package Str;

public class KMP {
    //求一个字符串是不是另一个字符串的字串
//    整体复杂度O(N) 因为O(M)是不可能超过O(N)的
    public static int getIndexOf(String s,String m){
        if (s == null || m == null || m.length() >s.length() || m.length() < 1){
            return -1;
        }
        char[] str1 = s.toCharArray();
        char[] str2 = m.toCharArray();
        int i1= 0;
        int i2 = 0;
        int[] next = getNextArray(str2);//O(M)
        while (i1 < str1.length && i2 < str2.length){
            //i2 == str2.length的时候代表着,肯定匹配到了
            //O(N)
            if (str1[i1] == str2[i2]){
                //如果相等,继续往后匹配
                i1++;
                i2++;
            }else if (next[i2] == -1){//等同于 i2 == 0
                //如果没有前缀和后缀匹配的,那没办法,只能往后走了, 没有办法往前跳了,只能换一个开头
                i1++;
            }else {
                //如果不等,则 i 位置字符可以不懂,i2往前跳
                i2 = next[i2];
            }
        }
        // i1越界 或 i2 越界
        return i2 == str2.length ? i1-i2:-1;
    }
    public static int[] getNextArray(char[] ms){
        if (ms.length == 1){
            return new int[]{-1};
        }
        int[] next = new int[ms.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cn = 0;//即代表往前跳的值
        while (i < next.length){
            if (ms[i-1] == ms[cn]){// 前一个
                next[i++] = ++cn;
            }else if (cn > 0){
                //当前跳到cn位置的字符,和i-1位置的对应不上,cn继续往前跳
                cn = next[cn];
            }else {
                //当cn为-1的时候,代表跳到了0下标的位置了
                next[i++] = 0;
            }
        }
        return next;
    }

    public static void main(String[] args) {
        String  s = "leetcode";
        String  m = "leeto";
        getIndexOf(s,m);
    }
}
